﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1.Algorithm
{
    public class Serach_Kth_PrimeNum    //第K个素数
    {
        public void SearchPrimeNumber_K()
        {
            int n = 10000;
            var t = new Stopwatch();    //可以测量一个时间间隔的运行时间，也可以测量多个时间间隔的总运行时间。
            t.Start();
            //var result = PrimeFilter(n);  //18-20ms
            var result = PrimeSqrt(n);    //58-60ms
            t.Stop();

            //                                                          最后使用 Elapsed 属性检查运行时间
            Console.WriteLine("第{0}个素数是{1}。计算耗时{2}毫秒", n, result, t.Elapsed.Milliseconds);
        }


        private List<long> Primes = new List<long> { 2, 3 };
        /*
         * 筛选法的思路：            
         * 先建一个足够大的表，把表内的素数全部标记出来，然后选出第K个
         * 把N个自然数按次序排列起来，1不是质数也不是合数要划去，2是质数，保留，然后把所有能被2整除的数都划去。
         * 2后面没被划去的第一个数是3，把3留下，能被3整除的都划去。
         * 这样一直下去，就会把不超过N的全部合数都筛选掉，留下来就是不超过N的全部质数。
        */ 
        private long PrimeFilter(int n)
        {
            if (n < 1)
            {
                throw new NotSupportedException("n不能小于1");
            }

            //      集合中最大的质数+2(过滤掉偶数)  很好的控制集合最大数量的写法
            for (var i = Primes[Primes.Count - 1] + 2; Primes.Count < n; i++)
            {
                bool isPrime = true;
                foreach (long j in Primes)
                {
                    //这个过滤条件和除以2到自身根号的判别方法是同样性质，可以提高20多倍的效率(18-20ms : 680-700ms)
                    if (j * j > i)  
                        break;

                    if (i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }

                if (isPrime)
                    Primes.Add(i);
            }

            return Primes[n - 1];
        }

        /*
         * 除以2到自身根号的数，如果都不能除尽说明是素数 
        */
        private int PrimeSqrt(int n)
        {
            int num = 3;         
            int count = 1;

            while (count <= n)
            {
                bool isPrime = true;
                int sqrt = Convert.ToInt32(Math.Sqrt(num));

                for (int i = sqrt; i >2 ; i--)
                {
                    if (num % i == 0)
                        isPrime = false;
                }
                if (isPrime)
                    count++;

                num += 2;
            }
            return num;
        }
        
    }
}
